BOJ

[Silver V] 새치기하지 마!!! - 33622

문제 링크

성능 요약

메모리: 14588 KB, 시간: 108 ms

분류

수학, 애드 혹, 확률론

제출 일자

2025년 9월 27일 18:53:34

문제 설명

경기과학고의 급식은 그 맛이 호텔 레스토랑과 비견된다고 전해질 정도로 굉장한 맛을 자랑한다. 피클은 여느 때처럼 급식을 먹기 위해 늘어진 줄이 줄어들기를 기다리고 있었다. 하지만 피클의 뒤쪽에 서 있는 사람들 중 한 명, 바로 재우가 기다림을 참지 못하고 새치기를 시도하고 있었다! 피클은 누군가 자신의 순번을 거슬러 가는 것을 용납하지 않기에, 새치기를 들켰다간 재우가 무사하지 못하게 될 것이다.

새치기가 일어나기 전 피클과 재우 사이에는 $N$명의 사람이 존재한다. 새치기는 아래 시행의 반복을 통해 일어난다.

현재 피클과 재우 사이에 사람이 $n$명일 때 재우가 $k$명을 제치고자 시도한다면 피클은 $\frac{k}{n+1}$의 확률로 재우를 잡아낼 것이다. 이 시행에서 재우가 잡히지 않았다면 재우와 피클 사이에 있는 사람의 수는 $k$명 줄어들어 $n-k$ 명이 된다. (단, $1\le k\le n$) 사람을 제치는 시행을 $X$번 함으로써 재우가 $N$명을 제치고 피클의 바로 뒤에 위치하게 된다면, 피클은 더 이상 재우의 범행을 눈치채지 못하게 된다.

우리는 재우가 무사하기를 바라기 때문에, 피클에게 잡힐 확률이 가장 낮도록 새치기하는 방법을 재우에게 알려주려고 한다. 따라서 가장 안전한 새치기 방법에서 사람을 제치는 행동의 횟수와 사람을 제치는 각 시행에서 제치는 사람의 수를 모두 구하여 알려주도록 하자. 정답이 여러 개 존재한다면 그중 아무거나 출력해도 상관없다.

입력

초기에 피클과 재우 사이에 존재하는 사람의 수 $N$이 주어진다.

출력

첫 번째 줄에 재우가 피클에게 잡힐 확률이 최소일 때 새치기를 한 횟수 $X$를 출력한다.

두 번째 줄에 $X$개의 정수 $k_1,k_2,\cdots ,k_X$를 공백으로 구분하여 출력한다. 이때, $k_i$는 재우가 $i$번째로 사람을 제칠 때 제친 사람의 수를 의미한다. $(1\le i\le X)$ 

소스 코드

• 새치기하지 마！！！.java